//给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。 
//
// 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-10,-3,0,5,9]
//输出：[0,-3,9,-10,null,5]
//解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,3]
//输出：[3,1]
//解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁴ 
// -10⁴ <= nums[i] <= 10⁴ 
// nums 按 严格递增 顺序排列 
// 
// Related Topics 树 二叉搜索树 数组 分治 二叉树 👍 1035 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution108 {
    /**
     * 迭代法
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0) return null;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> leftQueue = new LinkedList<>();
        Queue<Integer> rightQueue = new LinkedList<>();
        TreeNode root = new TreeNode(0);
        nodeQueue.offer(root);
        leftQueue.offer(0);
        rightQueue.offer(nums.length-1);
        while (!nodeQueue.isEmpty()){
            TreeNode cur = nodeQueue.poll();
            int leftIndex = leftQueue.poll();
            int rightIndex = rightQueue.poll();
            int mid = leftIndex+(rightIndex-leftIndex)/2;

            cur.val = nums[mid];

            if (leftIndex <= mid-1) {
                cur.left = new TreeNode(0);
                nodeQueue.offer(cur.left);
                leftQueue.offer(leftIndex);
                rightQueue.offer(mid-1);
            }
            if (rightIndex >= mid+1) {
                cur.right = new TreeNode(0);
                nodeQueue.offer(cur.right);
                leftQueue.offer(mid+1);
                rightQueue.offer(rightIndex);
            }
        }
        return root;
    }


        /**
         * 递归法
         * @param nums
         * @return
         */
    public TreeNode sortedArrayToBST2(int[] nums) {
        if(nums.length == 0) return null;
         return traversal(nums, 0, nums.length-1);
    }

    private TreeNode traversal(int[] nums, int left, int right) {
        if(right - left < 0) return null;
        int mid = (right+left)/2; //这样写不对！！！！
//        int mid = (left+(right-left)/2);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums,left,mid-1);
        root.right = traversal(nums,mid+1,right);
        return root;
    }

    public static void main(String[] args) {
        int[] arr = {-10,-3,0,5,9};
        TreeNode treeNode = new Solution108().sortedArrayToBST(arr);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
